import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/23 14:44
 * @description 字符串哈希 + 序列 DP
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        String[] words = {"cat","cats","catsdogcats","dog","dogcatsdog"};
        solution.findAllConcatenatedWordsInADict(words);
    }
    Set<Long> set = new HashSet<>();
    int P = 131, OFFSET = 128;
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        for (String s : words) {
            // 对于words中的每个s，计算对应的哈希值
            long hash = 0;
            for (char c: s.toCharArray()) {
                // 添加偏移量为了减少哈希碰撞
                hash = hash * P + (c - 'a') + OFFSET;
            }
            set.add(hash);
        }
        List<String> ans = new ArrayList<>();
        for (String s : words) {
            if (check(s)) {
                ans.add(s);
            }
        }
        return ans;
    }

    private boolean check(String s) {
        // 利用序列DP来判断一个单词是否是连接词
        int n = s.length();
        // f[i]表示 考虑s中前i个字符，能够切分出来的最大item个数
        int[] f = new int[n + 1];
        Arrays.fill(f, -1);
        // 0个字符，能够切分出0个单词
        f[0] = 0;
        for (int i = 0; i <= n; i++) {
            if (f[i] == -1) {
                continue;
            }
            long cur = 0;
            for (int j = i + 1; j <= n; j++) {
                cur = cur * P + (s.charAt(j - 1) - 'a') + OFFSET;
                if (set.contains(cur)) {
                    // 如果当前哈希值在set中出现过，那么说明f[j]可以 f[i] + s[i+1..n]切分
                    f[j] = Math.max(f[j], f[i] + 1);
                }
            }
            if (f[n] > 1) {
                return true;
            }
        }
        return false;
    }
}
